package com.yulan.dp.string;

import org.junit.Test;

/**
 * 最长子回文串
 */
public class LPS {
    public String DpLPS(String s){
        int n = s.length();
        boolean[][]  dp = new boolean[n][n];
        String ans = "";

        for(int len = 1; len<=n; len++){

            for(int i = 0; i<n; i++){
                int j = i + len -1;//结束的位置
                if(j>=s.length()) break;
                dp[i][j] = (len == 1 || len == 2 || dp[i+1][j-1] ) && s.charAt(i) == s.charAt(j);
                if(dp[i][j] && len > ans.length())
                    ans = s.substring(i,j+1);
            }
        }

        return ans;
    }

    public String QuickLPS(String s){
        if(s == null || s.length() == 0)
            return "";
        int[] range = new int[2];
        char[] str = s.toCharArray();

        for(int i = 0; i<s.length(); i++){
            i = findLongest(str, i, range);
        }
        return s.substring(range[0],range[1]+1);
    }

    private int findLongest(char[] str, int low, int[] range){
        int high = low;
        //查找中间相同的部分
        while (high < str.length - 1 && str[high + 1] == str[low]) {
            high++;
        }

        int ans = high;
        //向两边扩展
        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
            low--;
            high++;
        }
//         记录最大长度
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }

    @Test
    public void test(){
        String s = "babad";
        System.out.println(QuickLPS(s));
    }
}
